package com.googlecode.pathmachine.nn;

/**
 *Name: GeneticAlgorithm
 *
 *Author: John Pendlebury ported to Java from code written by Matt Buckland
 *
 *Description: Represents a group of Chromosomes that can be bread over generations.
 *
 *You can reuse this code provided you include these comments.
 *I'd also appreciate you letting me know via email just because I'm
 *interested.
 *
 *email: john.pendlebury2@mail.dcu.ie
 */
import java.util.*;

public class GeneticAlgorithm {
    //this holds the entire population of chromosomes

    private List<Genome> population = new ArrayList<Genome>();
    //size of population
    private int populationSize;
    //amount of weights per chromo
    private int chromosomeLength;
    //total fitness of population
    private double totalFitness;
    //best fitness this population
    private double bestFitness;
    //average fitness
    private double averageFitness;
    //worst
    private double worstFitness;
    //keeps track of the best genome
    private int fittestGenomeIndex;
    //probability that a chromosones bits will mutate.
    //Try figures around 0.05 to 0.3 ish
    private double mutationRate;
    //probability of chromosones crossing over bits
    //0.7 is pretty good
    private double crossoverRate;
    //generation counter
    private int generation;

    private void crossover(List<Double> mum,
            List<Double> dad,
            List<Double> baby1,
            List<Double> baby2) {
        //just return parents as offspring dependent on the rate
        //or if parents are the same
        if ((Utils.generateRandom() > crossoverRate) || (mum == dad)) {
            baby1.addAll(mum);
            baby2.addAll(dad);

            return;
        }

        //determine a crossover point
        int crossoverPoint = Utils.generateRandom(0, chromosomeLength - 1);

        //create the offspring
        for (int i = 0; i < crossoverPoint; ++i) {
            baby1.add(mum.get(i));
            baby2.add(dad.get(i));
        }

        for (int i = crossoverPoint; i < mum.size(); ++i) {
            baby1.add(dad.get(i));
            baby2.add(mum.get(i));
        }

    }

    private void mutate(List<Double> chromosome) {
        //traverse the chromosome and mutate each weight dependent
        //on the mutation rate
        for (int i = 0; i < chromosome.size(); ++i) {
            //do we perturb this weight?
            if (Utils.generateRandom() < mutationRate) {
                //add or subtract a small value to the weight
                chromosome.set(i, chromosome.get(i) + (Utils.generateRandomClamped() * Params.maxPerturbation));
            }
        }
    }

    private Genome getChromoRoulette() {
        //generate a random number between 0 & total fitness count
        double slice = (Utils.generateRandom() * totalFitness);

        //this will be set to the chosen chromosome
        Genome theChosenOne = null;

        //go through the chromosones adding up the fitness so far
        double fitnessSoFar = 0;

        for (Genome genome : population) {
            fitnessSoFar += genome.getFitness();

            //if the fitness so far > random number return the chromo at 
            //this point
            if (fitnessSoFar >= slice) {
                theChosenOne = genome;
                break;
            }
        }

        return theChosenOne;
    }

    //use to introduce elitism
    private void grabNBest(int n,
            int numCopies,
            List<Genome> newPopulation) {
        assert n < populationSize;

        //add the required amount of copies of the n most fittest 
        //to the supplied List
        while ((n--) != 0) {
            for (int i = 0; i < numCopies; ++i) {
                newPopulation.add(population.get(populationSize - 1 - n));
            }
        }
    }

    private void calculateBestWorstAvTot() {
        totalFitness = 0;

        double highestSoFar = 0;
        double lowestSoFar = 9999999;

        for (int i = 0; i < populationSize; ++i) {
            //update fittest if necessary
            if (population.get(i).getFitness() > highestSoFar) {
                highestSoFar = population.get(i).getFitness();
                fittestGenomeIndex = i;
                bestFitness = highestSoFar;
            }

            //update worst if necessary
            if (population.get(i).getFitness() < lowestSoFar) {
                lowestSoFar = population.get(i).getFitness();
                worstFitness = lowestSoFar;
            }

            totalFitness += population.get(i).getFitness();

        }//next chromo

        averageFitness = totalFitness / populationSize;
    }

    private void reset() {
        totalFitness = 0;
        bestFitness = 0;
        worstFitness = 9999999;
        averageFitness = 0;
        fittestGenomeIndex = 0;
    }

    public GeneticAlgorithm(int populationSize,
            double mutationRate,
            double crossoverRate,
            int numWeights) {
        this.populationSize = populationSize;
        this.mutationRate = mutationRate;
        this.crossoverRate = crossoverRate;
        this.chromosomeLength = numWeights;

        reset();

        //initialise population with chromosomes consisting of random
        //genes and all fitnesses set to zero
        for (int i = 0; i < populationSize; ++i) {
            population.add(new Genome());

            for (int j = 0; j < chromosomeLength; ++j) {
                population.get(i).addGene(Utils.generateRandomClamped());
            }
        }
    }

    //this runs the GA for one generation.
    public List<Genome> epoch(List<Genome> oldPopulation) {
        //assign the given population to the classes population
        population = oldPopulation;

        //reset the appropriate variables
        reset();

        //sort the population (for scaling and elitism)
        Collections.sort(population);

        //calculate best, worst, average and total fitness
        calculateBestWorstAvTot();

        //create a temporary List to store new chromosones
        List<Genome> newPopulation = new ArrayList<Genome>();

        //Now to add a little elitism we shall add in some copies of the
        //fittest genomes. Make sure we add an EVEN number or the roulette
        //wheel sampling will crash
        if ((Params.numCopiesElite * Params.numElite % 2) == 0) {
            grabNBest(Params.numElite, Params.numCopiesElite, newPopulation);
        }


        //now we enter the GA loop

        //repeat until a new population is generated
        while (newPopulation.size() < populationSize) {
            //grab two chromosones
            Genome mum = getChromoRoulette();
            Genome dad = getChromoRoulette();

            //create some offspring via crossover
            List<Double> baby1 = new ArrayList<Double>();
            List<Double> baby2 = new ArrayList<Double>();

            crossover(mum.getGenes(), dad.getGenes(), baby1, baby2);

            //now we mutate
            mutate(baby1);
            mutate(baby2);

            //now copy into vecNewPop population
            newPopulation.add(new Genome(baby1, 0));
            newPopulation.add(new Genome(baby2, 0));
        }

        //finished so assign new pop back into m_vecPop
        population = newPopulation;

        return population;
    }

    //-------------------accessor methods
    public List<Genome> getChromosomes() {
        return population;
    }

    public double averageFitness() {
        return totalFitness / populationSize;
    }

    public double bestFitness() {
        return bestFitness;
    }
}
